#ifndef S21_RBTREE_H
#define S21_RBTREE_H

#include <initializer_list>
#include <utility>

namespace s21 {

template <typename T, typename V>
class RBTree {
 protected:
  struct Node {
    T key;
    V value;
    std::pair<T, V> data;
    Node *parent;
    Node *left;
    Node *right;
    char color;
  };
  enum NodeColor { RED, BLACK };
  typedef Node *Node_ptr;

 public:
  RBTree();
  ~RBTree();
  RBTree(const RBTree &other);
  RBTree(RBTree &&other);
  void Clear();
  Node_ptr MaxNode(Node_ptr src);
  bool Empty();
  std::size_t Size();
  RBTree<T, V> &operator=(RBTree<T, V> &&other);
  RBTree<T, V> &operator=(const RBTree<T, V> &other);
  Node_ptr Minimum(Node_ptr node);
  Node_ptr Minimum(Node_ptr node) const;
  void TreeSizeCount(Node *node, std::size_t &count);

  class RBTreeIterator {
   public:
    RBTreeIterator();
    RBTreeIterator(Node_ptr start_node, Node_ptr null_node);

    T GetKey() const;
    V GetValue() const;
    Node_ptr GetNode();
    bool HasNext();
    Node_ptr Next();

    RBTreeIterator &operator++();
    RBTreeIterator operator++(int);
    RBTreeIterator &operator--();
    RBTreeIterator operator--(int);
    bool operator!=(const RBTreeIterator &other) const;
    T &operator*() const;
    std::pair<T, V> *operator->() const;
    bool operator==(const RBTreeIterator &other) const;

   private:
    Node_ptr current;
    Node_ptr final_leaf;
  };

  class ConstIterator {
   public:
    ConstIterator();
    ConstIterator(const Node_ptr start_node, const Node_ptr null_node);

    const T GetKey() const;
    const V GetValue() const;
    Node_ptr GetNode() const;
    bool HasNext() const;
    Node_ptr Next();

    ConstIterator &operator++();
    ConstIterator operator++(int);
    ConstIterator &operator--();
    ConstIterator operator--(int);
    bool operator!=(const ConstIterator &other) const;
    bool operator==(const ConstIterator &other) const;
    const T &operator*() const;
    const std::pair<T, V> *operator->() const;

   private:
    Node_ptr current;
    Node_ptr null_const_it;
  };

  ConstIterator cbegin() const;
  ConstIterator cend() const;
  RBTreeIterator begin();
  RBTreeIterator end();
  void Erase(RBTreeIterator pos);
  void Swap(RBTree &other);
  bool Contains(const T &key) const;
  RBTreeIterator Find(const T &key);
  std::size_t MaxSize();
  void Merge(RBTree &other);
  std::pair<RBTreeIterator, bool> Insert(const T &key, const V &value);
  void InsertNode(T key, V value);
  std::pair<RBTreeIterator, bool> InsertMulti(const T &key, const V &value);
  RBTreeIterator LowerBound(const T &key);
  RBTreeIterator UpperBound(const T &key);
  std::pair<RBTreeIterator, RBTreeIterator> EqualRange(const T &key);
  std::size_t Count(const T &key);

 protected:
  Node_ptr root;
  Node *final_leaf;

 private:
  void Allocate();
  void ClearNode(Node *node);
  void LeftRotate(Node_ptr x);
  void RightRotate(Node_ptr x);
  void DeleteNode(T data);
  void BlackNodeInDel(Node_ptr x);
  void ReplacingNodes(Node_ptr u, Node_ptr v);
  // void OperateDeleting(Node_ptr node, T key);
  void OperateRedParent(Node_ptr k);
  Node_ptr CreateNode(const T &key, const V &value);
  void AttachNode(Node_ptr node, Node_ptr parent);
  Node_ptr FindAttachmentPlace(T key);
};

template <typename T, typename V>
void RBTree<T, V>::Allocate() {
  final_leaf = new Node;
  final_leaf->color = BLACK;
  final_leaf->left = nullptr;
  final_leaf->right = nullptr;
  root = final_leaf;
}

template <typename T, typename V>
void RBTree<T, V>::ClearNode(Node *node) {
  if (node != final_leaf) {
    ClearNode(node->left);
    ClearNode(node->right);
    delete node;
  }
}

template <typename T, typename V>
void RBTree<T, V>::TreeSizeCount(Node *node, std::size_t &count) {
  if (node != final_leaf) {
    TreeSizeCount(node->left, count);
    count++;
    TreeSizeCount(node->right, count);
  }
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::Minimum(Node_ptr node) {
  if (node == final_leaf) return node;
  while (node->left != final_leaf) node = node->left;
  return node;
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::Minimum(Node_ptr node) const {
  if (node == final_leaf) return node;
  while (node->left != final_leaf) node = node->left;
  return node;
}

template <typename T, typename V>
void RBTree<T, V>::LeftRotate(Node_ptr x) {
  Node_ptr y = x->right;
  x->right = y->left;
  if (y->left != final_leaf) y->left->parent = x;
  y->parent = x->parent;
  if (x->parent == nullptr)
    this->root = y;
  else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;
  y->left = x;
  x->parent = y;
  y = nullptr;
}

template <typename T, typename V>
void RBTree<T, V>::RightRotate(Node_ptr x) {
  Node_ptr y = x->left;
  x->left = y->right;
  if (y->right != final_leaf) y->right->parent = x;

  y->parent = x->parent;
  if (x->parent == nullptr)
    this->root = y;
  else if (x == x->parent->right)
    x->parent->right = y;
  else
    x->parent->left = y;
  y->right = x;
  x->parent = y;
  y = nullptr;
}

template <typename T, typename V>
void RBTree<T, V>::DeleteNode(T key) {
  Node_ptr node_to_delete = final_leaf;
  Node_ptr x, y, node;
  node = root;
  while (node != final_leaf) {
    if (node->key == key) node_to_delete = node;
    node = (node->key <= key) ? node->right : node->left;
  }
  if (node_to_delete != final_leaf) {
    y = node_to_delete;
    int y_original_color = y->color;
    if (node_to_delete->left == final_leaf) {
      x = node_to_delete->right;
      ReplacingNodes(node_to_delete, x);
    } else if (node_to_delete->right == final_leaf) {
      x = node_to_delete->left;
      ReplacingNodes(node_to_delete, x);
    } else {
      y = Minimum(node_to_delete->right);
      y_original_color = y->color;
      x = y->right;
      if (y->parent == node_to_delete) {
        x->parent = y;
        y->right->parent = y;
      } else {
        ReplacingNodes(y, x);
        y->right = node_to_delete->right;
        y->right->parent = y;
      }
      ReplacingNodes(node_to_delete, y);
      y->left = node_to_delete->left;
      y->left->parent = y;
      y->color = node_to_delete->color;
    }
    if (node_to_delete != nullptr) delete node_to_delete;
    if (y_original_color == BLACK) BlackNodeInDel(x);
    node = nullptr;
  }
}

template <typename T, typename V>
void RBTree<T, V>::BlackNodeInDel(Node_ptr x) {
  Node_ptr brother;
  while (x != root && x->color == BLACK) {
    if (x == x->parent->left) {
      brother = x->parent->right;
      if (brother->color == RED) {
        brother->color = BLACK;
        x->parent->color = RED;
        LeftRotate(x->parent);
        brother = x->parent->right;
      }
      if (brother->left->color == BLACK && brother->right->color == BLACK) {
        brother->color = RED;
        x = x->parent;
      } else {
        if (brother->right->color == BLACK) {
          brother->left->color = BLACK;
          brother->color = RED;
          RightRotate(brother);
          brother = x->parent->right;
        }
        brother->color = x->parent->color;
        x->parent->color = BLACK;
        brother->right->color = BLACK;
        LeftRotate(x->parent);
        x = root;
      }
    } else {
      brother = x->parent->left;
      if (brother->color == RED) {
        brother->color = BLACK;
        x->parent->color = RED;
        RightRotate(x->parent);
        brother = x->parent->left;
      }
      if (brother->right->color == BLACK) {
        brother->color = RED;
        x = x->parent;
      } else {
        brother->color = x->parent->color;
        x->parent->color = BLACK;
        brother->left->color = BLACK;
        RightRotate(x->parent);
        x = root;
      }
    }
  }
  x->color = BLACK;
}

template <typename T, typename V>
void RBTree<T, V>::ReplacingNodes(Node_ptr old_node, Node_ptr new_node) {
  if (old_node->parent == nullptr)
    root = new_node;
  else if (old_node == old_node->parent->left)
    old_node->parent->left = new_node;
  else
    old_node->parent->right = new_node;
  new_node->parent = old_node->parent;
}

template <typename T, typename V>
RBTree<T, V> &RBTree<T, V>::operator=(RBTree &&other) {
  if (this != &other) {
    Clear();
    root = other.root;
    final_leaf = other.final_leaf;
    other.root = nullptr;
    other.final_leaf = nullptr;
  }
  return *this;
}

template <typename T, typename V>
RBTree<T, V> &RBTree<T, V>::operator=(const RBTree &other) {
  Clear();
  for (auto it = other.cbegin(); it.HasNext(); it.Next()) {
    InsertNode(it.GetKey(), it.GetValue());
  }
  return *this;
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::CreateNode(const T &key,
                                                         const V &value) {
  Node_ptr node = new Node;
  node->key = key;
  node->value = value;
  node->data = std::make_pair(node->key, node->value);
  node->parent = nullptr;
  node->left = final_leaf;
  node->right = final_leaf;
  node->color = RED;
  return node;
}

template <typename T, typename V>
void RBTree<T, V>::AttachNode(Node_ptr node, Node_ptr parent) {
  node->parent = parent;
  if (parent == nullptr)
    root = node;
  else if (node->key < parent->key)
    parent->left = node;
  else
    parent->right = node;
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::FindAttachmentPlace(T key) {
  Node_ptr y = nullptr;
  Node_ptr x = this->root;
  while (x != final_leaf) {
    y = x;
    if (key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  return y;
}

template <typename T, typename V>
RBTree<T, V>::RBTree() {
  Allocate();
}

template <typename T, typename V>
RBTree<T, V>::RBTree(const RBTree &other) {
  Allocate();
  for (auto it = other.cbegin(); it.HasNext(); it.Next()) {
    InsertNode(it.GetKey(), it.GetValue());
  }
}

template <typename T, typename V>
RBTree<T, V>::RBTree(RBTree &&other) {
  root = other.root;
  final_leaf = other.final_leaf;

  other.root = nullptr;
  other.final_leaf = nullptr;
}

template <typename T, typename V>
RBTree<T, V>::~RBTree() {
  Clear();
}

template <typename T, typename V>
void RBTree<T, V>::Clear() {
  ClearNode(root);
  delete final_leaf;
  root = nullptr;
  final_leaf = nullptr;
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::MaxNode(Node_ptr node) {
  Node_ptr result;
  if (node == final_leaf || node->right == final_leaf) {
    result = node;
  } else
    result = MaxNode(node->right);
  return result;
}

template <typename T, typename V>
bool RBTree<T, V>::Empty() {
  return root == final_leaf;
}

template <typename T, typename V>
std::size_t RBTree<T, V>::Size() {
  std::size_t count = 0;
  TreeSizeCount(root, count);
  return count;
}

template <typename T, typename V>
RBTree<T, V>::RBTreeIterator::RBTreeIterator()
    : current(nullptr), final_leaf(nullptr) {}

template <typename T, typename V>
RBTree<T, V>::RBTreeIterator::RBTreeIterator(Node_ptr start_node,
                                             Node_ptr null_node) {
  current = start_node;
  final_leaf = null_node;
}

template <typename T, typename V>
T RBTree<T, V>::RBTreeIterator::GetKey() const {
  return current->key;
}

template <typename T, typename V>
V RBTree<T, V>::RBTreeIterator::GetValue() const {
  return current->value;
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::RBTreeIterator::GetNode() {
  return current;
}

template <typename T, typename V>
bool RBTree<T, V>::RBTreeIterator::HasNext() {
  return (current != nullptr && current != final_leaf);
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::RBTreeIterator::Next() {
  Node_ptr ret_val = current;
  if (current->right != final_leaf) {
    current = current->right;
    while (current->left != final_leaf) current = current->left;
  } else {
    Node_ptr p = current->parent;
    while (p != nullptr && current == p->right) {
      current = p;
      p = p->parent;
    }
    current = p;
  }
  return ret_val;
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator &
RBTree<T, V>::RBTreeIterator::operator++() {
  if (current->right != final_leaf) {
    current = current->right;
    while (current->left != final_leaf) current = current->left;
  } else {
    Node_ptr p = current->parent;
    while (p != nullptr && current == p->right) {
      current = p;
      p = p->parent;
    }
    current = p;
  }
  return *this;
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::RBTreeIterator::operator++(
    int) {
  RBTreeIterator tmp = *this;
  ++(*this);
  return tmp;
}

template <typename T, typename V>
bool RBTree<T, V>::RBTreeIterator::operator!=(
    const RBTreeIterator &other) const {
  return current != other.current;
}

template <typename T, typename V>
bool RBTree<T, V>::RBTreeIterator::operator==(
    const RBTreeIterator &other) const {
  return current == other.current;
}

template <typename T, typename V>
T &RBTree<T, V>::RBTreeIterator::operator*() const {
  if (current == nullptr) {
    static T res{};
    return res;
  }
  return current->key;
}

template <typename T, typename V>
std::pair<T, V> *RBTree<T, V>::RBTreeIterator::operator->() const {
  // std::pair<T, V> *result = new std::pair<T, V>;
  //  *result = std::make_pair(current->key, current->value);
  //  return result;
  return &(current->data);
}

template <typename T, typename V>
RBTree<T, V>::ConstIterator::ConstIterator()
    : current(nullptr), null_const_it(nullptr) {}

template <typename T, typename V>
RBTree<T, V>::ConstIterator::ConstIterator(
    const RBTree<T, V>::Node_ptr start_node,
    const RBTree<T, V>::Node_ptr null_node) {
  current = start_node;
  null_const_it = null_node;
}

template <typename T, typename V>
const T RBTree<T, V>::ConstIterator::GetKey() const {
  return current->key;
}

template <typename T, typename V>
const V RBTree<T, V>::ConstIterator::GetValue() const {
  return current->value;
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::ConstIterator::GetNode() const {
  return current;
}

template <typename T, typename V>
bool RBTree<T, V>::ConstIterator::HasNext() const {
  return (current != nullptr && current != null_const_it);
}

template <typename T, typename V>
typename RBTree<T, V>::Node_ptr RBTree<T, V>::ConstIterator::Next() {
  Node_ptr ret_val = current;
  if (current->right != null_const_it) {
    current = current->right;
    while (current->left != null_const_it) current = current->left;
  } else {
    Node_ptr p = current->parent;
    while (p != nullptr && current == p->right) {
      current = p;
      p = p->parent;
    }
    current = p;
  }
  return ret_val;
}

template <typename T, typename V>
typename RBTree<T, V>::ConstIterator &
RBTree<T, V>::ConstIterator::operator++() {
  if (current->right != null_const_it) {
    current = current->right;
    while (current->left != null_const_it) current = current->left;
  } else {
    Node_ptr p = current->parent;
    while (p != nullptr && current == p->right) {
      current = p;
      p = p->parent;
    }
    current = p;
  }
  return *this;
}

template <typename T, typename V>
typename RBTree<T, V>::ConstIterator RBTree<T, V>::ConstIterator::operator++(
    int) {
  RBTreeIterator tmp = *this;
  ++(*this);
  return tmp;
}

template <typename T, typename V>
bool RBTree<T, V>::ConstIterator::operator!=(
    const RBTree<T, V>::ConstIterator &other) const {
  return current != other.current;
}

template <typename T, typename V>
bool RBTree<T, V>::ConstIterator::operator==(
    const RBTree<T, V>::ConstIterator &other) const {
  return current == other.current;
}

template <typename T, typename V>
const T &RBTree<T, V>::ConstIterator::operator*() const {
  if (current == nullptr) {
    static T res{};
    return res;
  }
  return current->key;
}

template <typename T, typename V>
const std::pair<T, V> *RBTree<T, V>::ConstIterator::operator->() const {
  return &(current->data);
}

template <typename T, typename V>
typename RBTree<T, V>::ConstIterator RBTree<T, V>::cbegin() const {
  return ConstIterator(Minimum(root), final_leaf);
}

template <typename T, typename V>
typename RBTree<T, V>::ConstIterator RBTree<T, V>::cend() const {
  ConstIterator it = cbegin();
  while (it.HasNext()) it.Next();
  return it;
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::begin() {
  return RBTreeIterator(Minimum(root), final_leaf);
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::end() {
  RBTreeIterator it = begin();
  while (it.HasNext()) it.Next();
  return it;
}

template <typename T, typename V>
std::size_t RBTree<T, V>::MaxSize() {
  return std::numeric_limits<size_t>::max() / sizeof(Node);
}

template <typename T, typename V>
bool RBTree<T, V>::Contains(const T &key) const {
  Node *current = root;
  bool contains = false;
  while (current != final_leaf && !contains) {
    if (key < current->key)
      current = current->left;
    else if (key > current->key)
      current = current->right;
    else
      contains = true;
  }
  return contains;
}

template <typename T, typename V>
void RBTree<T, V>::Swap(RBTree &other) {
  std::swap(root, other.root);
  std::swap(final_leaf, other.final_leaf);
}

template <typename T, typename V>
void RBTree<T, V>::Erase(RBTreeIterator pos) {
  Node *node = pos.GetNode();
  if (node != final_leaf && node != nullptr) DeleteNode(node->key);
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::Find(const T &key) {
  Node_ptr curr = root;
  bool contains = false;
  while (curr != final_leaf && !contains) {
    if (key < curr->key)
      curr = curr->left;
    else if (key > curr->key)
      curr = curr->right;
    else
      contains = true;
  }
  typename RBTree<T, V>::RBTreeIterator result_iterator;
  if (contains)
    result_iterator = RBTreeIterator(curr, final_leaf);
  else
    result_iterator = end();
  return result_iterator;
}

template <typename T, typename V>
void RBTree<T, V>::Merge(RBTree &other) {
  RBTree copy_tree(other);
  RBTree mergedTree;
  for (auto it = this->begin(); it.HasNext(); it.Next()) {
    mergedTree.Insert(it.GetKey(), it.GetValue());
  }
  for (auto it = copy_tree.begin(); it.HasNext(); it.Next()) {
    std::pair<RBTreeIterator, bool> tmp =
        mergedTree.Insert(it.GetKey(), it.GetValue());
    if (tmp.second) {
      other.Erase(tmp.first);
    }
  }
  *this = std::move(mergedTree);
}

template <typename T, typename V>
void RBTree<T, V>::OperateRedParent(Node_ptr inserted_node) {
  Node_ptr uncle;
  while (inserted_node != root && inserted_node->parent->color == RED) {
    if (inserted_node->parent == inserted_node->parent->parent->right) {
      uncle = inserted_node->parent->parent->left;
      if (uncle->color == RED) {
        uncle->color = BLACK;
        inserted_node->parent->color = BLACK;
        inserted_node->parent->parent->color = RED;
        inserted_node = inserted_node->parent->parent;
      } else {
        if (inserted_node == inserted_node->parent->left) {
          inserted_node = inserted_node->parent;
          RightRotate(inserted_node);
        }
        inserted_node->parent->color = BLACK;
        inserted_node->parent->parent->color = RED;
        LeftRotate(inserted_node->parent->parent);
      }
    } else {
      uncle = inserted_node->parent->parent->right;
      if (uncle->color == RED) {
        uncle->color = BLACK;
        inserted_node->parent->color = BLACK;
        inserted_node->parent->parent->color = RED;
        inserted_node = inserted_node->parent->parent;
      } else {
        if (inserted_node == inserted_node->parent->right) {
          inserted_node = inserted_node->parent;
          LeftRotate(inserted_node);
        }
        inserted_node->parent->color = BLACK;
        inserted_node->parent->parent->color = RED;
        RightRotate(inserted_node->parent->parent);
      }
    }
  }
  root->color = BLACK;
}

template <typename T, typename V>
std::pair<typename RBTree<T, V>::RBTreeIterator, bool> RBTree<T, V>::Insert(
    const T &key, const V &value) {
  RBTreeIterator it;
  bool contains = Contains(key);
  if (contains) {
    it = Find(key);
  } else {
    Node_ptr node = CreateNode(key, value);
    Node_ptr attachment_place = FindAttachmentPlace(key);
    AttachNode(node, attachment_place);
    it = std::move(RBTreeIterator(node, final_leaf));
    if (node->parent == nullptr) {
      node->color = BLACK;
    } else {
      if (node->parent->parent != nullptr) OperateRedParent(node);
    }
  }
  return std::make_pair(it, !contains);
}

template <typename T, typename V>
void RBTree<T, V>::InsertNode(T key, V value) {
  Node_ptr node = CreateNode(key, value);
  Node_ptr attachment_place = FindAttachmentPlace(key);
  AttachNode(node, attachment_place);
  if (node->parent == nullptr) {
    node->color = BLACK;
  } else if (node->parent->parent != nullptr)
    OperateRedParent(node);
}

template <typename T, typename V>
std::size_t RBTree<T, V>::Count(const T &key) {
  size_t cnt = 0;
  Node *current = root;
  while (current != final_leaf) {
    if (current->key == key) cnt++;
    if (key < current->key)
      current = current->left;
    else
      current = current->right;
  }
  return cnt;
}

template <typename T, typename V>
std::pair<typename RBTree<T, V>::RBTreeIterator,
          typename RBTree<T, V>::RBTreeIterator>
RBTree<T, V>::EqualRange(const T &key) {
  Node *lower = nullptr;
  Node *upper = nullptr;
  Node *current = root;

  bool repeat = true;
  while (current != final_leaf && repeat) {
    if (current->key < key) {
      current = current->right;
    } else if (key < current->key) {
      upper = current;
      current = current->left;
    } else {  // ==
      lower = current;
      repeat = false;
    }
  }

  return std::make_pair(RBTreeIterator(lower, final_leaf),
                        RBTreeIterator(upper, final_leaf));
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::LowerBound(const T &key) {
  Node *y = nullptr;
  Node *x = root;

  while (x != final_leaf) {
    if (x->key >= key) {
      y = x;
      x = x->left;
    } else
      x = x->right;
  }
  RBTreeIterator it(y, final_leaf);
  return it;
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::UpperBound(const T &key) {
  Node *y = nullptr;
  Node *x = root;

  while (x != final_leaf) {
    if (key < x->key) {
      y = x;
      x = x->left;
    } else
      x = x->right;
  }

  RBTreeIterator it(y, final_leaf);
  return it;
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator &
RBTree<T, V>::RBTreeIterator::operator--() {
  if (current->left != final_leaf) {
    current = current->left;
    while (current->right != final_leaf) {
      current = current->right;
    }
  } else {
    Node_ptr p = current->parent;
    while (p != nullptr && current == p->left) {
      current = p;
      p = p->parent;
    }
    current = p;
  }
  return *this;
}

template <typename T, typename V>
typename RBTree<T, V>::RBTreeIterator RBTree<T, V>::RBTreeIterator::operator--(
    int) {
  RBTreeIterator tmp = *this;
  --(*this);
  return tmp;
}

template <typename T, typename V>
typename RBTree<T, V>::ConstIterator &
RBTree<T, V>::ConstIterator::operator--() {
  if (current->left != final_leaf) {
    current = current->left;
    while (current->right != final_leaf) {
      current = current->right;
    }
  } else {
    Node_ptr p = current->parent;
    while (p != nullptr && current == p->left) {
      current = p;
      p = p->parent;
    }
    current = p;
  }
  return *this;
}

template <typename T, typename V>
typename RBTree<T, V>::ConstIterator RBTree<T, V>::ConstIterator::operator--(
    int) {
  RBTreeIterator tmp = *this;
  --(*this);
  return tmp;
}

template <typename T, typename V>
std::pair<typename RBTree<T, V>::RBTreeIterator, bool>
RBTree<T, V>::InsertMulti(const T &key, const V &value) {
  Node_ptr node = CreateNode(key, value);
  Node_ptr attachment_place = FindAttachmentPlace(key);
  AttachNode(node, attachment_place);
  RBTreeIterator it(node, final_leaf);
  std::pair<typename RBTree<T, V>::RBTreeIterator, bool> result;
  if (node->parent == nullptr) {
    node->color = BLACK;
    result = std::make_pair(it, true);
  } else if (node->parent->parent == nullptr)
    result = std::make_pair(it, true);
  else {
    OperateRedParent(node);
    result = std::make_pair(it, true);
  }
  return result;
}
}  // namespace s21
#endif  // S21_RBTREE_H